from typing import List


def singleNonDuplicate(self, nums: List[int]) -> int:
    left, right = 0, len(nums) - 1
    n = len(nums)
    while left < right:
        mid = (left + right) // 2
        if mid % 2 == 0:
            if mid + 1 < n and nums[mid] == nums[mid + 1]:
                left = mid + 1
            else:
                right = mid
        else:
            if mid - 1 > -1 and nums[mid] == nums[mid - 1]:
                left = mid + 1
            else:
                right = mid
    return nums[right]
